  \chapter{Método Proposto}
  
  O método proposto se utiliza das metaheurísticas GRASP e ILS e da abordagem exata através da programação linear inteira. Ela visa tirar proveito das vantagens de cada uma dessas técnicas. A abordagem exata tem a capacidade de encontrar a solução ótima e as metaheurísticas são em geral mais rápidas que as técnicas exatas. Da mesma forma que as outras abordagens heurísticas esse novo algoritmo consome pouco tempo computacional e possui uma forma de escapar de mínimos locais.
  
  O framework utilizado foi o GRASP, com a fase de busca local adaptada para executar em conjunto com o ILS. A hibridização das metaheurísticas citadas com a programação linear inteira provê uma aceleração na obtenção de boas soluções através de uma intensificação em uma direção totalmente arbitraria. O uso dessas técnicas também proporciona um alto grau de convergência em relação a qualidade das soluções.

  A busca local se utiliza de 3 estruturas de vizinhança, o \textit{swap-x}, o \textit{crossover} e a \textit{compactação}, que serão explicadas nas próximas seções.
  
\section{Fase de construção}
  
  A construção da solução inicial é feita elemento a elemento utilizando o GRASP. O primeiro passo é a ordenação do conjunto de voos da instância a partir do tempo de partida sugerido.  
  
  Inicialmente todos os voos são adiantados, levando em consideração o atraso máximo permitido, e após a montagem do trilho é feita a relaxação dos atrasos e dos adiantamentos envolvidos. Na prática apenas uma pequena parte das modificações do horário de partida sugerido é incorporado a solução.
  
  Existe duas formas de fazer a montagem da solução, uma é a montagem trilho a trilho, onde um novo trilho só poderia ser criado quando o anterior já está saturado. A outra forma é a montagem de trilhos de forma paralela, que, a priori, provoca uma melhor distribuição dos voos. Na pratica a primeira abordagem é adotada, pois, nas instâncias disponíveis ela sempre apresentou soluções de melhor qualidade. Uma maior quantidade de testes envolvendo outros tipos de instâncias ainda é necessário para decidir se existe, por exemplo, a necessidade de alterar a estratégia escolhida de acordo com alguma característica da instância.
  
  Outro aspecto interessante que tem que ser levado em consideração são as manutenções das aeronaves, elas são incorporadas no framework através da criação de voos fictícios com origem e destino no aeroporto da manutenção e com a duração igual ao tempo da manutenção. Isso é possível pois os trilhos não são associados a aeronaves específicas.
  
\subsection{Formação dos trilhos de forma sequencial}

Quando se pensa na escolha do primeiro voo do trilho a decisão imediata é a escolha do voo que contenha o menor horário de partida sugerido. Porém essa escolha reduz a quantidade de soluções que podem ser geradas, pois a escolha dos voos remanescentes do trilho é diretamente influenciada pela escolha do voo inicial.

A abordagem utilizada para a escolha do primeiro voo inicia com a criação de uma lista de candidatos iniciais (LCI) que é formada pelos 5 voos, que ainda não estejam presentes em nenhum outro trilho, e que tenham o menor tempo de partida sugerido. A escolha do voo inicial é feita de forma aleatória entre os elementos da LCI.


\subsection{Formação dos trilhos de forma paralela}
  
  Essa estratégia monta uma conjunto de trilhos e constroi eles de forma paralela, esses trilhos são iniciados com voos que não podem coexistir em um mesmo trilho. Em cada iteração é feita a escolha de um trilho e então um voo é escolhido para ser acrescentado a ele. Caso não existam candidatos aptos para serem adicionados a esse trilho então ele é removido do conjunto de trilhos que estão em construção. 
  Vale lembrar que um novo trilho é criado sempre que se identifica um voo que não pode ser adicionado em nenhum dos trilhos correntes.
  
\subsection{Escolha dos voos de um trilho}

 As seções anteriores explicaram como é feita a escolha do primeiro voo de um trilho. Os demais demais voos são escolhidos com base no tipo de arco e na lista restrita de candidatos. 
 
 Os tipos de arcos foram definidos no Capítulo \ref{cap:descprob}, porém nessa etapa apenas os 4 primeiros são considerados. As variáveis  $A_{1}, A_{2}, A_{3}, A_{4}$ representam os arcos do tipo 1 a 4 respectivamente. Os arcos do tipo 5 e 6 só são utilizados apenas na modelagem matemática. Os arcos do tipo 1 permitem a ligação de voos sem a utilização de atrasos e/ou reposicionamentos. Os arcos do tipo 2 utilizam atrasos mas não o reposicionamento. Os arcos do tipo 3 permitem o sequenciamento com a utilização de um voo de reposicionamento mas sem inserir atraso em nenhum dos voos envolvidos. Os arcos do tipo 4 utilizam-se de atrasos e de um voo de reposicionamento para fazer a ligação entre dois voos.
 
 O primeiro passo na escolha de um voo é a definição do tipo de arco que irá ser utilizado. Essa escolha é feita tendo como base as probabilidades de escolha dos tipos de arcos $P(A_{1}), P(A_{2}), P(A_{3}), P(A_{4})$. Esses valores foram obtidos a partir da porcentagem dos tipos de arcos presentes em uma solução ótima de um problema real.
 
 De posse do tipo de arco, é feita então a formação da lista de candidatos. Essa lista é ordenada de acordo com o seu horário de partida sugerido, caso o arco seja do tipo $A_{1}$, ou pelo custo associado a sua escolha para os demais tipos de arco. No caso da lista de candidatos não possuir nenhum voo, então outro tipo de arco é sorteado, até que não seja possível acrescentar nenhum voo ao trilho. Quando isso ocorre a construção desse trilho é finalizada.
 
 Caso seja possível a obtenção de uma lista de candidatos então ela é filtrada tendo como base o passo 4 a 6 do algoritmo \ref{alg:graspcons}. Como a lista de voos se encontra ordenada, então, o elemento de menor impacto ($v_{menor}$) na solução é o primeiro e o de maior impacto ($v_{maior}$) é o último. Dessa forma é formada a lista restrita de candidatos, ela contem apenas os elementos que possuem valor de impacto de até $v_{menor} + \alpha*(v_{maior} + v_{menor})$. Um candidato é escolhido aleatoriamente dessa lista e adicionado a solução corrente. O valor de $\alpha$ ainda é objeto de estudo, mas bons resultados tem sido obtido para $\alpha$ igual a 0.5.
 
 A finalização da fase de construção se da quando se percebe a alocação de todos os voos. Quando isso ocorre é feito um relaxamento nos trilhos com a finalidade de remover modificações nos horários de partida que não são necessários. 
 
 \section{Fase de busca local}
 
A fase de busca local tem o objetivo de melhorar a solução obtida na fase de construção. No método proposto essa fase foi substituída pelo ILS. Ou seja primeiro são aplicados as estruturas de vizinhança, vizando obter o valor ótimo local da solução. Depois é feita uma pertubação que diversifica a solução corrente. Quando nenhuma das duas estratégias consegue melhorar a solução então a busca local encerra e uma nova iteração do GRASP pode ser iniciada.

Como essa pertubação é feita com o a utilização do método exato em um dado sub-problema, então além da diversificação ainda temos uma melhora no valor da função objetivo.
 
 \subsection{Vizinhança}
 
 Foram definidas 3 estruturas de vizinhança o Swap-X, o Cross-Over e a Compactação. O Swap-X e o Cross-Over, tem o objetivo de remover modificações nos horários de partida sugeridos dos voos, bem como a remoção de voos de reposicionamentos, e a Compactação, promove a redução do número de trilhos da solução. Abaixo essa estruturas são explicadas.
 
\subsubsection{Swap-X}

Esse operador efetua a troca de X voos de um trilho por um conjunto de voos de outro trilho. No método proposto apenas os movimentos do tipo Swap-1 e Swap-2 são utilizados, pois essa vizinhança apresentou melhores resultados. Essa modificação, quando bem utilizada, permite a remoção de atrasos e de voos de reposicionamento melhorando assim a solução.
%Na Figura X um caso de melhoria no custo dos trilhos é exemplificada. 
 
 \subsubsection{Cross-Over}
 
 A idéia do operador $crossover$ é a de efetuar troca entre dois segmentos de trilhos com a finalidade de gerar novos trilhos com menos modificações no horário de partida. São selecionados dois trilhos e cada um é divido em duas partes que são trocadas.
 
  %A Figura X ilustra uma melhoria causada por um movimento desse tipo.
 
 \subsubsection{Compactação}
 
 A compactação é a única estrutura de vizinhança utilizada que é capaz de reduzir a quantidade de trilhos da solução final.
 
 Isso ocorre porque ela consegue, insere um trilho em outro de forma direta ou com a utilização de voos de reposicionamento. Ela causa um grande impacto na função objetivo.
 
%A figura X mostra a redução de um trilho com a utilização desse movimento.
 
 \subsection{Pertubação usando o método exato}
   
 A pertubação é utilizada quando as estruturas de vizinhança não conseguem melhorar a solução. Quando isso ocorre pode-se dizer que a solução corrente é a ótima local com relação a vizinhança definida.
 
 Para tentar encontrar outros mínimos locais aplica-se uma modificação na estrutura da solução, mesmo que isso provoque uma piora na sua qualidade, e depois procura-se melhora-la aplicando novamente uma busca local.
 
 O método de pertubação utilizado aqui difere do que normalmente é aplicado pois a modificação na estrutura da solução inicial é feita de tal forma que a qualidade da solução final é sempre melhor ou igual a inicial.
 
 A sua utilização ocorre com a seleção de um conjunto de trilhos, que juntos definem um sub-problema, e a posterior aplicação do método exato descrito no Capítulo \ref{cap:modelomat} nesse conjunto reduzido. O método exato irá retornar a configuração ótima desses voos, que serão agrupados novamente a solução inicial.
 
 A escolha dos voos é feita com base no \textit{grau de compactação} dos trilhos que compõem a solução. O grau de compactação é definido como sendo a porcentagem de utilização efetiva de um trilho com relação ao tempo de partida do primeiro voo e o tempo de chegada do último voo da instância. O cálculo do grau de compactação não leva em consideração os voos de reposicionamento, pois eles não são passados para o solver.
 
	Os trilhos são adicionados a solução até o limite de 80 voos, pois o solver consegue resolver rapidamente problemas desse porte. Essa quantidade foi escolhida de forma empírica.
	
	A seleção dos trilhos, tendo como base o grau de compactação, pode ocorrer de 3 formas:
	
	\begin{itemize}
\item Adição dos trilhos com maior grau de compactação.
\item Adição dos trilhos com menor grau de compactação.
\item Alternar entre a adição de um trilho com maior grau de compactação com outro de menor grau de compactação.
\end{itemize}
 
 A utilização da segunda abordagem proporcionou melhores resultados. O uso do solver é feito de forma sucessiva, enquanto a solução corrente estiver sendo melhorada. Quando ela não melhora mais a solução é retornada para que seja realizada outra busca local.

Caso utilização do solver não altere a solução corrente então a iteração do GRASP é dada como encerrada.  
 